#!/usr/bin/python


#R.Huang 
""" Since the list is not hashable in the graph search, I change to tuple"""

from utils import *;
from orig_search import *;

class SixteenPuzzle(Problem):
	"""The problem of solving a eight puzzle problem """
	def __init__(self, state):
		self.initial = tuple(state)
		self.pos_dict = []
		for x in range(16):
			self.pos_dict.append( tuple( (x // 4, x % 4 ) ) )
				
	def successor(self, state):
		"""In the 8 puzzle problem, move the blank to other position."""
		result = []
		#print ">", state
		position = list(state).index(0) 
		for action, newposition in self.possible_position(position).iteritems():
			new = list(state[:])
			new[newposition], new[position] = new[position], new[newposition]
			result.append((action, tuple(new)))
		return result
		
	def possible_position(self, position):
		"""return the possible position"""
		result = {};
		col = position % 4;
		row = position // 4;
		# add the action in a circle manner. No dead iter now
		if row != 3:
			result['D'] = position +4
		if col != 0: 
			result['L'] = position -1	
		if row != 0:
			result['U'] = position -4
		if col != 3:
			result['R'] = position +1
		return result
	
	def shuffle(self):
		for i in range(1000):
			succ = self.successor( self.initial )
			chosen = random.randrange(0,len(succ),1)
			#print chosen, " is randly chosen"
			self.initial = succ[chosen][1]
			#print self.initial

	def goal_test(self, state):
		""" Test if this is the goal state"""
		#print "Testing goal", state
		for i in range(16):
			if state[i] != i:
				return False
		return True;
			
	def h(self, node):
		"""Heuristic function"""
		# print node.state
		#temp=list(node.state)
		sum=0
		for x in range(16): # mahatten distance
			#print "Bug"
			#sum = sum + abs(temp.index(x)-x)
			pile = node.state[x]
			if pile==0:
				continue
			row_delta = abs(self.pos_dict[x][0] - self.pos_dict[pile][0] )
			col_delta = abs(self.pos_dict[x][1] - self.pos_dict[pile][1] )
			sum += (row_delta + col_delta)
		return sum

pos_dict1 = []
for x in range(16):
	pos_dict1.append( tuple( (x // 4, x % 4 ) ) )
	
def h2(node):
	"""Heuristic function"""
	# print node.state
	#temp=list(node.state)
	sum=0
	for x in range(16): # mahatten distance
		#sum = sum + abs(temp.index(x)-x)
		pile = node.state[x]
		row_delta = abs(pos_dict1[x][0] - pos_dict1[pile][0] )
		col_delta = abs(pos_dict1[x][1] - pos_dict1[pile][1] )
		sum += (row_delta + col_delta)
	return sum
			
def all_perms(l):
	if len(l) <=1:
		yield l
	else:
		for perm in all_perms(l[1:]):
			for i in range(len(perm)+1):
				yield perm[:i] + l[0:1] + perm[i:]

mapping = {0:0, 1:1, 2:2, 3:3, 4:7, 5:6, 6:5, 7:4, 8:8, 9:9 , 10:10, 11:11, 12:15, 13:14 , 14:13 , 15:12 }

def solvable(l):
	newl = [l[mapping[i]] for i in xrange(16) if l[mapping[i]]!=0]
	#print "Going to test", newl
	return not oddreverse(l)
		
def oddreverse(l):
	print l
	t = len(l)
	count = 0
	for i in xrange(2, t):
		for j in xrange(2, i):
			if l[j]>l[i]:
				count +=1
	if count%2 ==0:
		return True
	return False

def rdn_state_generator():
	s = range(16)
	while True:
		random.shuffle(s)
		if solvable(s):
			return tuple(s)

import cPickle

def getfullset():
	if os.path.exists("fullset"):
		f = open('fullset', 'rb')
		return cPickle.load(f)
	else:
		init = [i for i in xrange(9)]
		fullset = [tuple(state) for state in all_perms(init) if solvable(state)]
		print "After generation", len(fullset)
		output = open('fullset', 'wb')
		cPickle.dump(fullset, output)
		return fullset

if (__name__=="__main__"):
	init = rdn_state_generator()
	#init = (2,12,11,14,6,15,10,5,3,9,0,13,8,7,1,4)
	#init = (2,3,4,0,1,5,7,8,9,6,10,12,13,14,11,15)
	#init = ( 1, 2, 3, 7, 4, 5, 6, 11, 8, 9, 10, 15,12,0,13,14)
	#print solvable(init)
	init = (2,3,4,0,1,5,7,8,9,6,10,12,13,14,11,15)
	#init = ( 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
	init = (4, 1, 9, 2, 8, 6, 11, 3, 12, 14, 13, 7, 10, 0, 5, 15)
	print solvable(init)
	instance = SixteenPuzzle(init)
	#instance.shuffle()
	#print instance.initial
	print "Start Search!!!!!!!!!!!!!!!!!!!!"
	a = astar_search( instance, instance.h )
	print len(a.path())